package algorithm;
//背包问题
public class knapsackProblem {
    public static void main(String[] args) {
        int[] val =new int[]{1500,3000,2000};//物品价格
        int[] w = new int[]{1,4,3};//物品重量
        int m=4;//背包容量
        int n = val.length;//物品个数
        //m+1表示行   n+1表示列
        //第0行0列不放数据所以+1
        int[][] v = new int[n+1][m+1];
        int[][] path = new int[n+1][m+1];
        //先将二维数组0行0列设置为0，因为数组默认为0，这里就不设置了
        //根据公式动态规划处理
        for(int i =1;i<v.length;i++){//i表示前几个物品
            for(int j=1;j<v[0].length;j++){//j表示当前容量
                if(w[i-1]>j){//当前物品重量大于当前容量
                    v[i][j]=v[i-1][j];
                }else {//当前物品重量小于或等于当前容量
                    //val[i-1]+v[i-1][j-w[i-1]]:这个物品的价格+上个单元剩余容量的最大价值
                    //val[i-1]:表示这个物品的价格
                    //v[i-1][j-w[i-1]]：表示上个单元剩余容量的最大价值
                        //[j-w[i-1]]:表示剩余容量(最大容量减去当前容量)
//                    v[i][j]=Math.max(i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                    if(v[i-1][j]>=val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=v[i-1][j];
                    }else {
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        path[i][j]=1;
                    }
                }
            }
        }
        //输出v查看情况
        for(int i =0;i<v.length;i++){
            for(int j = 0;j<v[0].length;j++){
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("=====");
        int i=path.length-1;
        int j = path[0].length-1;
        while (i>0&&j>0){
            if (path[i][j]==1){
                System.out.println("第"+i+"个商品放入背包");
                //总重量减去当前物品质量
                j=j-w[i-1];
            }
            //因为最佳途径在行的最后所以i--；
            i--;
        }
    }
}
